// https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

// 思路
// 1. 使用后序遍历的最后一个元素作为根节点。
// 2. 在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树。
// 3. 根据中序遍历的分割位置，递归构建左子树和右子树。
// 4. 返回构建好的二叉树根节点。
package binarytree

func ConstructBinaryTreeFromInPostOrder(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 || len(postorder) == 0 {
		return nil
	}

	// 后序遍历的最后一个元素是根节点
	rootVal := postorder[len(postorder)-1]
	root := &TreeNode{Val: rootVal}

	// 在中序遍历中找到根节点的位置
	var rootIndex int
	for i, val := range inorder {
		if val == rootVal {
			rootIndex = i
			break
		}
	}

	// 构建左子树和右子树
	root.Left = ConstructBinaryTreeFromInPostOrder(inorder[:rootIndex], postorder[:rootIndex])
	root.Right = ConstructBinaryTreeFromInPostOrder(inorder[rootIndex+1:], postorder[rootIndex:len(postorder)-1])

	return root
}
